/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function (heights) {
  let pre = []
  let res = []
  let w = heights.length, h = heights[0].length
  // 初始化并查集
  for (let i = 0; i < w * h; i++) {
    pre[i] = i
  }
  for (let i = 0; i < w; i++) {
    for (let j = 0; j < h; j++) {
      let cur_pos = i * h + j
      if (j - 1 >= 0) { // 左边结点
        let left = cur_pos - 1
        res.push({ val1: cur_pos, val2: left, weight: Math.abs(heights[i][j] - heights[i][j - 1]) })
      }
      if (i - 1 >= 0) {
        let up = (i - 1) * h + j
        res.push({ val1: cur_pos, val2: up, weight: Math.abs(heights[i][j] - heights[i - 1][j]) })
      }
    }
  }
  res.sort((a, b) => a.weight - b.weight)
  const find = (x) => {
    if (pre[x] != x) {
      pre[x] = find(pre[x])
    }
    return pre[x]
  }
  const union = (x, y) => {
    let rootX = find(x)
    let rootY = find(y)
    if (rootX !== rootY) {
      pre[rootY] = rootX
    }
  }
  const isConnected = (x, y) => {
    return find(x) === find(y)
  }
  for (let edge of res) {
    // 将相连的顶点并起来
    union(edge.val1, edge.val2)
    if (isConnected(0, w * h - 1)) {
      return edge.weight
    }
  }
  return 0
}
/**
 * 想了半天发现不是动态规划
 * 图 并查集
 */
console.log(minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]])) // 1
console.log(minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]])) // 2
console.log(minimumEffortPath([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]])) // 0
console.log(minimumEffortPath([[4, 3, 4, 10, 5, 5, 9, 2], [10, 8, 2, 10, 9, 7, 5, 6], [5, 8, 10, 10, 10, 7, 4, 2], [5, 1, 3, 1, 1, 3, 1, 9], [6, 4, 10, 6, 10, 9, 4, 6]]))
